{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "58b7453e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-06-26T12:12:56.604699Z",
     "start_time": "2021-06-26T12:12:56.438942Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gcount=20\n",
      "G.all_colors=[2, 4, 2, 4, 1, 3, 4, 3, 3, 4, 1, 2, 4, 2, 3, 1, 2, 0, 0, 4]\n",
      "         1742 function calls (1741 primitive calls) in 0.006 seconds\n",
      "\n",
      "   Ordered by: standard name\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "       46    0.000    0.000    0.001    0.000 <__array_function__ internals>:2(prod)\n",
      "        1    0.000    0.000    0.003    0.003 <ipython-input-4-820d00ce18b2>:21(RandGenAdj)\n",
      "        1    0.000    0.000    0.002    0.002 <ipython-input-4-820d00ce18b2>:53(nearFilltry)\n",
      "        1    0.000    0.000    0.006    0.006 <ipython-input-4-820d00ce18b2>:69(main)\n",
      "        1    0.000    0.000    0.006    0.006 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 Graphy.py:124(__init__)\n",
      "        1    0.000    0.000    0.000    0.000 Graphy.py:141(__len__)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:154(addVertex)\n",
      "       26    0.000    0.000    0.000    0.000 Graphy.py:170(addEdge)\n",
      "        1    0.000    0.000    0.000    0.000 Graphy.py:186(count)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:204(linked_colors)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:205(<setcomp>)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:214(set_colorof)\n",
      "        1    0.000    0.000    0.000    0.000 Graphy.py:225(all_colors)\n",
      "        1    0.000    0.000    0.000    0.000 Graphy.py:227(<listcomp>)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:47(__init__)\n",
      "       48    0.000    0.000    0.000    0.000 Graphy.py:64(addLinked)\n",
      "       20    0.000    0.000    0.000    0.000 Graphy.py:73(paint)\n",
      "       68    0.000    0.000    0.000    0.000 Graphy.py:91(get_color)\n",
      "      118    0.000    0.000    0.000    0.000 Graphy.py:94(get_linked)\n",
      "       46    0.000    0.000    0.000    0.000 Random.py:5(getrestlist)\n",
      "       46    0.000    0.000    0.004    0.000 Random.py:8(choicerest)\n",
      "       46    0.000    0.000    0.000    0.000 _collections_abc.py:392(__subclasshook__)\n",
      "       46    0.000    0.000    0.000    0.000 abc.py:100(__subclasscheck__)\n",
      "      138    0.000    0.000    0.000    0.000 abc.py:96(__instancecheck__)\n",
      "       46    0.000    0.000    0.000    0.000 fromnumeric.py:2907(_prod_dispatcher)\n",
      "       46    0.000    0.000    0.001    0.000 fromnumeric.py:2912(prod)\n",
      "       46    0.000    0.000    0.001    0.000 fromnumeric.py:70(_wrapreduction)\n",
      "       46    0.000    0.000    0.000    0.000 fromnumeric.py:71(<dictcomp>)\n",
      "        5    0.000    0.000    0.001    0.000 iostream.py:195(schedule)\n",
      "        4    0.000    0.000    0.000    0.000 iostream.py:308(_is_master_process)\n",
      "        4    0.000    0.000    0.000    0.000 iostream.py:321(_schedule_flush)\n",
      "        4    0.000    0.000    0.001    0.000 iostream.py:384(write)\n",
      "        5    0.000    0.000    0.000    0.000 iostream.py:91(_event_pipe)\n",
      "        5    0.000    0.000    0.000    0.000 socket.py:438(send)\n",
      "        5    0.000    0.000    0.000    0.000 threading.py:1017(_wait_for_tstate_lock)\n",
      "        5    0.000    0.000    0.000    0.000 threading.py:1071(is_alive)\n",
      "        5    0.000    0.000    0.000    0.000 threading.py:513(is_set)\n",
      "      138    0.000    0.000    0.000    0.000 {built-in method _abc._abc_instancecheck}\n",
      "       46    0.000    0.000    0.000    0.000 {built-in method _abc._abc_subclasscheck}\n",
      "        1    0.000    0.000    0.006    0.006 {built-in method builtins.exec}\n",
      "       46    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}\n",
      "      162    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}\n",
      "    51/50    0.000    0.000    0.000    0.000 {built-in method builtins.len}\n",
      "        2    0.000    0.000    0.001    0.000 {built-in method builtins.print}\n",
      "       46    0.000    0.000    0.001    0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}\n",
      "        4    0.000    0.000    0.000    0.000 {built-in method posix.getpid}\n",
      "        5    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}\n",
      "       26    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}\n",
      "        5    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}\n",
      "       68    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}\n",
      "       46    0.002    0.000    0.003    0.000 {method 'choice' of 'numpy.random.mtrand.RandomState' objects}\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "       46    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}\n",
      "       20    0.000    0.000    0.000    0.000 {method 'randint' of 'numpy.random.mtrand.RandomState' objects}\n",
      "       46    0.000    0.000    0.000    0.000 {method 'reduce' of 'numpy.ufunc' objects}\n",
      "\n",
      "\n"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "'a' cannot be empty unless no samples are taken",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m--------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-4-820d00ce18b2>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     84\u001b[0m         \u001b[0mcProfile\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrunctx\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'main(20, 3)'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlocals\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     85\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m50\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 86\u001b[0;31m                 \u001b[0mmain\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m20\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-4-820d00ce18b2>\u001b[0m in \u001b[0;36mmain\u001b[0;34m(maxVnum, maxDegNum)\u001b[0m\n\u001b[1;32m     70\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     71\u001b[0m         \u001b[0mG\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mRandGenAdj\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmaxVnum\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmaxDegNum\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 72\u001b[0;31m         \u001b[0mnearFilltry\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     73\u001b[0m         \u001b[0mGcount\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcount\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mby\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m'v'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     74\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"{Gcount=}\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-4-820d00ce18b2>\u001b[0m in \u001b[0;36mnearFilltry\u001b[0;34m(G)\u001b[0m\n\u001b[1;32m     58\u001b[0m                         \u001b[0;32mcontinue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     59\u001b[0m                 \u001b[0;31m#print(used_clr)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 60\u001b[0;31m                 \u001b[0mw\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mArrayChoice\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mused_clr\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     61\u001b[0m                 \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mset_colorof\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0midx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mw\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     62\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/mnt/d/sourcecodes/git/four-colors/test/algorithm/Random.py\u001b[0m in \u001b[0;36mchoicerest\u001b[0;34m(used, src)\u001b[0m\n\u001b[1;32m     13\u001b[0m                 \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Wrong Error, Need (MutableSequence/Set, Container\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0mrest\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgetrestlist\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mused_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msrc_set\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mrand\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mchoice\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrest\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32mmtrand.pyx\u001b[0m in \u001b[0;36mnumpy.random.mtrand.RandomState.choice\u001b[0;34m()\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: 'a' cannot be empty unless no samples are taken"
     ]
    }
   ],
   "source": [
    "\n",
    "\n",
    "from algorithm.Random import choicerest as ArrayChoice\n",
    "from collections import abc\n",
    "from Graphy import GraphByVertex, Vertex\n",
    "from numpy import random as rand\n",
    "import cProfile\n",
    "from memory_profiler import *\n",
    "import numpy as np\n",
    "import sys\n",
    "\n",
    "\"\"\"\n",
    "现在已经有了一个随机生成连接情况的图\n",
    "下一步是上色。\n",
    "最后可视化就再说了吧。\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "colors = ['red', 'yellow', 'blue', 'green']#Enumeration...\n",
    "\n",
    "\n",
    "def RandGenAdj(max_v, max_deg):\n",
    "\n",
    "\t\"\"\"\n",
    "\tmax vertex  : max number of vertexes to be generated\n",
    "\tmax degree : max number of linked vertex a vertex can have\n",
    "\t\"\"\"\n",
    "\tmaxvset = set(list(range(max_v)))\n",
    "\tG = GraphByVertex(max_v)\n",
    "\tfor idx in range(max_v):\n",
    "\t\tG.addVertex(Vertex(idx, 0, []))\n",
    "\n",
    "\tfor idx in range(max_v):\n",
    "\t\tdegree_per_v = rand.randint(0, max_deg)#每个节点的邻接节点数， 0个到max_deg个\n",
    "\t\ttmp = {idx}\n",
    "\t\tfor i in range(degree_per_v):\n",
    "\t\t\tw = ArrayChoice(tmp, maxvset)\n",
    "\t\t\ttmp.add(w)\n",
    "\t\t\tG.addEdge(idx, w)\n",
    "\treturn G\n",
    "\n",
    "def RandGenAdj_LessZero(max_v, max_deg):\n",
    "\t\"\"\"\n",
    "\t上面的一种生成方式简单，但是可能生成过多的零邻接节点\n",
    "\t\"\"\"\n",
    "\tpass\n",
    "\n",
    "\n",
    "def randfill(G:GraphByVertex):\n",
    "\t#Start the Process of filling\n",
    "\tfor idx, clr in zip(G.G, rand.randint(1, 5, len(G))):\n",
    "\t\tG.set_colorof(idx.get_idx, clr)\n",
    "\n",
    "def nearFilltry(G:GraphByVertex):\n",
    "\t#在速度要求下可以用这种方式生成，但这种可能导致找不到解\n",
    "\tfor idx in range(len(G)):\n",
    "\t\tused_clr = G.linked_colors(idx) #used_clr is a list\n",
    "\t\tif used_clr is None:\n",
    "\t\t\tcontinue\n",
    "\t\t#print(used_clr)\n",
    "\t\tw = ArrayChoice(set(used_clr), {0, 1, 2, 3, 4})\n",
    "\t\tG.set_colorof(idx, w)\n",
    "\n",
    "def fill4clr(G:GraphByVertex):\n",
    "\t#能找到优解\n",
    "\tdegree_of_vertexes = G.idx_deg_mapping\n",
    "\tpass\n",
    "\n",
    "#@profile\n",
    "def main(maxVnum, maxDegNum):\n",
    "\n",
    "\tG = RandGenAdj(maxVnum, maxDegNum)\n",
    "\tnearFilltry(G)\n",
    "\tGcount = G.count(by='v')\n",
    "\tprint(f\"{Gcount=}\")\n",
    "\tprint(f\"{G.all_colors=}\")\n",
    "\t#rint(G)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "\tcProfile.runctx('main(20, 3)', None, locals())\n",
    "\tfor i in range(50):\n",
    "\t\tmain(20, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd381547",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
